import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/7 17:56
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode t4 = new TreeNode(4), t7 = new TreeNode(7),
                t5 = new TreeNode(5, t7, null), t6 = new TreeNode(6),
        t3 = new TreeNode(3, t5, t6), t2 = new TreeNode(2, t4, null),
                t1 = new TreeNode(1, t2, t3);
        solution.findBottomLeftValue(t1);
    }
    public int findBottomLeftValue(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int num = queue.size();
            boolean left = true;
            while (num > 0) {
                TreeNode temp = queue.poll();
                if (left && temp.left == null && temp.right == null) {
                    ans = temp.val;
                    left = false;
                }
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
                num--;
            }
        }
        return ans;
    }
}
